//===--- Sink.cpp ----- Code Sinking --------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
///
/// \file
/// Many PIL instructions that don't have side effects at the PIL level are
/// lowered to a sequence of LLVM instructions that does have side effects that
/// LLVM can't sink. This pass sinks instructions close to their users.
///
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "sink-instructions"

#include "polarphp/pil/lang/DebugUtils.h"
#include "polarphp/pil/lang/Dominance.h"
#include "polarphp/pil/lang/PILArgument.h"
#include "polarphp/pil/lang/PILDebugScope.h"
#include "polarphp/pil/lang/PILInstruction.h"
#include "polarphp/pil/optimizer/analysis/DominanceAnalysis.h"
#include "polarphp/pil/optimizer/analysis/LoopAnalysis.h"
#include "polarphp/pil/optimizer/analysis/PostOrderAnalysis.h"
#include "polarphp/pil/optimizer/passmgr/Transforms.h"
#include "polarphp/pil/optimizer/utils/InstOptUtils.h"
#include "llvm/ADT/Statistic.h"

using namespace polar;

STATISTIC(NumInstrSunk, "Number of instructions sunk");

namespace {

class CodeSinkingPass : public PILFunctionTransform {
public:
   CodeSinkingPass() = default;

   DominanceInfo *DT;
   PostOrderFunctionInfo *PO;
   PILLoopInfo *LoopInfo;

   /// returns True if were able to sink the instruction \p II
   /// closer to it's users.
   bool sinkInstruction(PILInstruction *II) {

      // We can't sink instructions that may read or write to memory
      // or side effects because it can change the semantics of the program.
      if (II->mayHaveSideEffects() || II->mayReadOrWriteMemory()) return false;

      // Some instructions don't have direct memory side effects but can't be sunk
      // because of other reasons.
      if (isa<MarkUninitializedInst>(II)  ||
          isa<MarkFunctionEscapeInst>(II) ||
          isa<MarkDependenceInst>(II)) return false;

      // We don't sink stack allocations to not destroy the proper nesting of
      // stack allocations.
      if (II->isAllocatingStack() || II->isDeallocatingStack())
         return false;

      PILBasicBlock *CurrentBlock = II->getParent();
      PILBasicBlock *Dest = nullptr;
      unsigned InitialLoopDepth = LoopInfo->getLoopDepth(CurrentBlock);

      // TODO: We may want to delete debug instructions to allow us to sink more
      // instructions.
      for (auto result : II->getResults()) {
         for (auto *Operand : result->getUses()) {
            PILInstruction *User = Operand->getUser();

            // Check if the instruction is already in the user's block.
            if (User->getParent() == CurrentBlock) return false;

            // Record the block of the first user and move on to
            // other users.
            if (!Dest) {
               Dest = User->getParent();
               continue;
            }

            // Find a location that dominates all users. If we did not find such
            // a block or if it is the current block then bail out.
            Dest = DT->findNearestCommonDominator(Dest, User->getParent());

            if (!Dest || Dest == CurrentBlock)
               return false;
         }
      }

      if (!Dest) return false;

      // We don't want to sink instructions into loops. Walk up the dom tree
      // until we reach the same loop nest level.
      while (LoopInfo->getLoopDepth(Dest) != InitialLoopDepth) {
         auto Node = DT->getNode(Dest);
         assert(Node && "Invalid dom tree");
         auto IDom = Node->getIDom();
         assert(IDom && "Can't find the idom");
         Dest = IDom->getBlock();

         if (!Dest || Dest == CurrentBlock)
            return false;
      }

      II->moveBefore(&*Dest->begin());
      NumInstrSunk++;
      return true;
   }

   void run() override {
      bool Changed = false;
      auto *F = getFunction();
      DT = PM->getAnalysis<DominanceAnalysis>()->get(F);
      PO = getAnalysis<PostOrderAnalysis>()->get(F);
      PILLoopAnalysis *LA = PM->getAnalysis<PILLoopAnalysis>();
      LoopInfo = LA->get(F);

      auto postOrder = PO->getPostOrder();

      // Scan the blocks in a post-order direction to make sure that we sink the
      // users of each instruction before visiting the instruction itself to allow
      // us to scan the function just once.
      for (auto &BB : postOrder) {
         auto Inst = BB->end();
         auto Begin = BB->begin();

         // Skip empty blocks.
         if (Inst == Begin) continue;
         // Point to the first real instruction.
         Inst--;

         while (true) {
            if (Inst == Begin) {
               // This is the first instruction in the block. Try to sink it and
               // move on to the next block.
               Changed |= sinkInstruction(&*Inst);
               break;
            } else {
               // Move the iterator to the next instruction because we may sink the
               // current instruction.
               PILInstruction *II = &*Inst;
               --Inst;
               Changed |= sinkInstruction(II);
            }
         }

      }

      if (Changed) PM->invalidateAnalysis(F,
                                          PILAnalysis::InvalidationKind::Instructions);
   }


};
} // end anonymous namespace

PILTransform *polar::createCodeSinking() {
   return new CodeSinkingPass();
}
